package _mst;

import java.util.Arrays;

/**
 * 面试题 08.01. 三步问题
 */
public class T0801 {
    public int waysToStep(int n) {
        int MOD = 1000000007;
        long[] f = new long[n + 4];
        f[0] = 1;
        for (int i = 0; i <= n; i++) {
            f[i + 3] = (f[i + 2] + f[i + 1] + f[i]) % MOD;
        }
        return (int) f[n + 3];
    }
}
